/**
  @(#)$Id: AL_ListDouble.h 74 2013-10-10 12:42:07Z xiaoting $
  @brief    Also called double-linked list doubly linked list is a list in which each data node in both two pointers that point to a 
  direct successor and direct precursors. Therefore, two-way linked list from any one of the node point, can easily access its 
  predecessor and successor nodes node.

  @Author $Author: xiaoting $
  @Date $Date: 2013-10-10 20:42:07 +0800 (周四, 10 十月 2013) $
  @Revision $Revision: 74 $
  @URL $URL: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_ListDouble.h $
  @Header $Header: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_ListDouble.h 74 2013-10-10 12:42:07Z xiaoting $
 */

#ifndef CXX_AL_LISTDOUBLE_H
#define CXX_AL_LISTDOUBLE_H

#ifndef CXX_AL_NODE_H
#include "AL_Node.h"
#endif

///////////////////////////////////////////////////////////////////////////
//			AL_ListDouble
///////////////////////////////////////////////////////////////////////////

template<typename T> 
class AL_ListDouble
{
public:
	static const DWORD LISTDOUBLE_POSITION_INVALID		= 0xffffffff;
	/**
	* Construction
	*
	* @param
	* @return
	* @note
	* @attention
	*/
	AL_ListDouble();

	/**
	* Destruction
	*
	* @param
	* @return
	* @note
	* @attention
	*/
	~AL_ListDouble();

	/**
	* Length
	*
	* @param VOID
	* @return DWORD
	* @note get the length of the list
	* @attention
	*/
	DWORD Length() const;
	
	/**
	* Find
	*
	* @param const T& tData <IN> 
	* @return DWORD
	* @note find the position of tData 
	* @attention  if not find, will be return 0xffffffff
	*/
	DWORD Find(const T& tData) const;

	/**
	* IsElement
	*
	* @param const T& tData <IN> 
	* @return BOOL
	* @note the tData  is in the list?
	* @attention
	*/
	BOOL IsElement(const T& tData) const;

	/**
	* Insert
	*
	* @param DWORD dwIndex <IN>
	* @param const T& tData <IN> 
	* @return BOOL
	* @note inset the tData  into the list at the position
	* @attention
	*/
	BOOL Insert(DWORD dwIndex,const T& tData);

	/**
	* InsertBegin
	*
	* @param const T& tData <IN> 
	* @return BOOL
	* @note inset the tData  into the list at the position
	* @attention
	*/
	BOOL InsertBegin(const T& tData);


	/**
	* InsertEnd
	*
	* @param const T& tData <IN> 
	* @return BOOL
	* @note inset the tData  into the list at the position
	* @attention
	*/
	BOOL InsertEnd(const T& tData);

	/**
	* Remove
	*
	* @param const T& tData <IN> 
	* @return BOOL
	* @note remove the tData in the list
	* @attention
	*/
	BOOL Remove(const T& tData);

	/**
	* RemoveAt
	*
	* @DWORD dwIndex <IN> 
	* @return BOOL
	* @note remove the tData in the list at the index (dwIndex)
	* @attention
	*/
	BOOL RemoveAt(DWORD dwIndex);

	/**
	* IsEmpty
	*
	* @param VOID
	* @return BOOL
	* @note the list has data?
	* @attention
	*/
	BOOL IsEmpty() const;

	/**
	* Get
	*
	* @param	DWORD dwIndex <IN>
	* @param	T& tTypeOut <OUT>
	* @return BOOL
	* @note get the T at the position
	* @attention the dwIndex must is little than the list length
	*/
	BOOL Get(DWORD dwIndex, T& tTypeOut) const;

	/**
	* Set
	*
	* @param	DWORD dwIndex <IN>
	* @param	const T& tData <IN>
	* @param	T& tTypeOut <OUT>
	* @return BOOL
	* @note Replaced with the element element element on position index, and returns the old element...
	* @attention Index must in the list
	*/
	BOOL Set(DWORD dwIndex, const T& tData, T& tTypeOut);

	/**
	* Clear
	*
	* @param VOID
	* @return VOID
	* @note clear the data in the list
	* @attention all data will be clear
	*/
	VOID Clear();

protected:
private:
	/**
	* GetNodeByIndex
	*
	* @param DWORD dwIndex <IN>
	* @return AL_Node<T>*
	* @note get the const T& at the position
	* @attention the dwIndex must is little than the list length
	*/
	AL_Node<T>* GetNodeByIndex(DWORD dwIndex) const;

	/**
	*Copy Construct
	*
	* @param const AL_ListDouble<T>& cAL_ListDouble
	* @return
	*/
	AL_ListDouble(const AL_ListDouble<T>& cAL_ListDouble);

	/**
	*Assignment
	*
	* @param const AL_ListDouble<T>& cAL_ListDouble
	* @return AL_ListDouble<T>&
	*/
	AL_ListDouble<T>& operator = (const AL_ListDouble<T>& cAL_ListDouble);

public:
protected:
private: 
	AL_Node<T>*		m_pHeader;
	DWORD			m_dwSize;
};

///////////////////////////////////////////////////////////////////////////
//			AL_ListDouble
///////////////////////////////////////////////////////////////////////////
/**
* Construction
*
* @param
* @return
* @note
* @attention
*/
template<typename T> 
AL_ListDouble<T>::AL_ListDouble():
m_pHeader(NULL),
m_dwSize(0x00)
{
	m_pHeader = new AL_Node<T>;
}

/**
* Destruction
*
* @param
* @return
* @note
* @attention
*/
template<typename T> 
AL_ListDouble<T>::~AL_ListDouble()
{
	Clear();
	//delete the header
	if (NULL != m_pHeader) {
		delete m_pHeader;
		m_pHeader = NULL;
	}
}

/**
* Length
*
* @param
* @return
* @note get the length of the list
* @attention
*/
template<typename T> DWORD 
AL_ListDouble<T>::Length() const
{
	return m_dwSize;
	/*
	if (TRUE == IsEmpty()) {
		return 0;
	}
	AL_Node<T>* pMove = NULL;
	DWORD dwCount = 1;

	pMove = m_pHeader->m_pNext;
	while (NULL != pMove->m_pNext) {
		dwCount ++;
		pMove = pMove->m_pNext;
	}
	return dwCount;
	*/
}

/**
* Find
*
* @param const T& tData <IN> 
* @return DWORD
* @note find the position of tData 
* @attention  if not find, will be return 0xffffffff
*/
template<typename T> DWORD 
AL_ListDouble<T>::Find(const T& tData) const
{
	if (TRUE == IsEmpty()) {
		return LISTDOUBLE_POSITION_INVALID;
	}
	
	AL_Node<T>* pMove = NULL;
	DWORD dwCount = 1;

	//loop the next data;
	pMove = m_pHeader->m_pNext;
	while (NULL != pMove->m_pNext) {
		if (tData == pMove->m_tData) {
			//find the data
			return dwCount-1;
		}
		dwCount ++;
		pMove = pMove->m_pNext;
	}
	
	//the end
	if (tData == pMove->m_tData) {
		//find the data
		return dwCount-1;
	}

	return LISTDOUBLE_POSITION_INVALID;
}

/**
* IsElement
*
* @param const T& tData <IN> 
* @return BOOL
* @note the tData  is in the list?
* @attention
*/
template<typename T> BOOL 
AL_ListDouble<T>::IsElement(const T& tData) const
{
	if (LISTDOUBLE_POSITION_INVALID == Find(tData )) {
		return FALSE;
	}

	return TRUE;
}

/**
* Insert
*
* @param const T& tData <IN> 
* @param DWORD dwIndex <IN>
* @return BOOL
* @note inset the tData  into the list at the position
* @attention
*/
template<typename T> BOOL 
AL_ListDouble<T>::Insert(DWORD dwIndex, const T& tData)
{
	if (dwIndex > Length()) {
		//can not insert to this position
		return FALSE;
	}
	AL_Node<T>* pInsert = new AL_Node<T>;
	pInsert->m_tData = tData;
	
	AL_Node<T>* pPre = NULL;
	//get the previous Node
	if (0x00 == dwIndex) {
		pPre = m_pHeader;
	}
	else {
		pPre = GetNodeByIndex(dwIndex - 1);
	}
	
	if ((NULL == pPre)) {
		//error
		return FALSE;
	}
	if (Length() == dwIndex){
		//end
		pPre->m_pNext = pInsert;
		pInsert->m_pPre = pPre;
	}
	else {
		//among of the list
		AL_Node<T>* pIndexNode = pPre->m_pNext;
		if ((NULL == pIndexNode)) {
			//error
			return FALSE;
		}
		pInsert->m_pNext = pIndexNode;
		pIndexNode->m_pPre = pInsert;

		pPre->m_pNext = pInsert;
		pInsert->m_pPre = pPre;
	}

	m_dwSize++;
	return TRUE;
}

/**
* InsertBegin
*
* @param const T& tData <IN> 
* @return BOOL
* @note inset the tData  into the list at the position
* @attention
*/
template<typename T> BOOL 
AL_ListDouble<T>::InsertBegin(const T& tData)
{
	return Insert(0, tData);
}

/**
* InsertEnd
*
* @param const T& tData <IN> 
* @return BOOL
* @note inset the tData  into the list at the position
* @attention
*/
template<typename T> BOOL 
AL_ListDouble<T>::InsertEnd(const T& tData)
{
	return Insert(Length(), tData);
}


/**
* Remove
*
* @param const T& tData <IN> 
* @return BOOL
* @note remove the tData in the list
* @attention
*/
template<typename T> BOOL 
AL_ListDouble<T>::Remove(const T& tData)
{
	if (TRUE == IsEmpty()) {
		return FALSE;
	}
	
	BOOL bRemove = FALSE;
	AL_Node<T>* pMove = NULL;
	DWORD dwCount = 1;

	//loop the next data;
	pMove = m_pHeader->m_pNext;
	while (NULL != pMove->m_pNext) {
		if (tData == pMove->m_tData) {
			pMove = pMove->m_pNext;
			//find the data
			bRemove = RemoveAt(dwCount-1);
			if (FALSE == bRemove) {
				return bRemove;
			}
		}
		else {
			pMove = pMove->m_pNext;
		}
		dwCount ++;
	}

	//the end
	if (tData == pMove->m_tData) {
		//find the data
		bRemove = RemoveAt(dwCount-1);
		if (FALSE == bRemove) {
			return bRemove;
		}
	}

	return bRemove;
}

/**
* RemoveAt
*
* @param DWORD dwIndex <IN> 
* @return BOOL
* @note remove the tData in the list at the index (dwIndex)
* @attention
*/
template<typename T> BOOL 
AL_ListDouble<T>::RemoveAt(DWORD dwIndex)
{
	if (dwIndex > Length()) {
		//can not insert to this position
		return FALSE;
	}

	AL_Node<T>* pDelete = GetNodeByIndex(dwIndex);
	if (NULL == pDelete) {
		//error
		return FALSE;
	}

	AL_Node<T>* pPre = NULL;
	//get the previous Node
	if (0x00 == dwIndex) {
		pPre = m_pHeader;
	}
	else {
		pPre = pDelete->m_pPre;
	}

	if (NULL == pPre) {
		//error
		return FALSE;
	}
	pPre->m_pNext = pDelete->m_pNext;

	AL_Node<T>* pNext = pDelete->m_pNext;
	if (NULL != pNext) {
		//among of the list
		pNext->m_pPre = pPre;
	}

	delete pDelete;
	pDelete = NULL;

	m_dwSize--;
	return TRUE;
}

/**
* IsEmpty
*
* @param
* @return BOOL
* @note the list has data?
* @attention
*/
template<typename T> BOOL 
AL_ListDouble<T>::IsEmpty() const
{
	return (NULL == m_pHeader->m_pNext) ? TRUE:FALSE;
}

/**
* Get
*
* @param	DWORD dwIndex <IN>
* @param	T& tTypeOut <OUT>
* @return BOOL
* @note get the T at the position
* @attention the dwIndex must is little than the list length
*/
template<typename T> BOOL
AL_ListDouble<T>::Get(DWORD dwIndex, T& tTypeOut) const
{
	if (TRUE == IsEmpty()) {
		//error
		return FALSE;
	}

	if (Length()-1 < dwIndex) {
		//error
		return FALSE;
	}
	
	AL_Node<T>* pGet = GetNodeByIndex(dwIndex);
	if (NULL == pGet) {
		//error
		return FALSE;
	}
	tTypeOut = pGet->m_tData;
	return TRUE;
}

/**
* Set
*
* @param	DWORD dwIndex <IN>
* @param	const T& tData <IN>
* @param	T& tTypeOut <OUT>
* @return BOOL
* @note Replaced with the element element element on position index, and returns the old element...
* @attention Index must in the list
*/
template<typename T> BOOL 
AL_ListDouble<T>::Set(DWORD dwIndex, const T& tData, T& tTypeOut)
{
	if (Length()-1 < dwIndex) {
		//error
		return FALSE;
	}
	
	AL_Node<T>* pSet = GetNodeByIndex(dwIndex);
	if (NULL == pSet) {
		//error
		return FALSE;
	}
	
	tTypeOut = pSet->m_tData;
	pSet->m_tData = tData;
	return TRUE;
}

/**
* Clear
*
* @param VOID
* @return VOID
* @note clear the data in the list
* @attention all data will be clear
*/
template<typename T> VOID 
AL_ListDouble<T>::Clear()
{
	if (TRUE == IsEmpty()) {
		//No data,
		return;
	}

	AL_Node<T>* pDelete = NULL;
	while(NULL != m_pHeader->m_pNext){
		//get the node
		pDelete = m_pHeader->m_pNext;
		m_pHeader->m_pNext = pDelete->m_pNext;
		delete pDelete;
		pDelete = NULL;
	}
	m_dwSize = 0x00;
}

/**
* GetNodeByIndex
*
* @param DWORD dwIndex <IN>
* @return AL_Node<T>* 
* @note get the const T& at the position
* @attention the dwIndex must is little than the list length
*/
template<typename T> AL_Node<T>* 
AL_ListDouble<T>::GetNodeByIndex(DWORD dwIndex) const
{
	if (Length()-1 < dwIndex) {
		//error
		return NULL;
	}

	AL_Node<T>* pMove = NULL;
	DWORD dwCount = 1;
	//loop the next data;
	pMove = m_pHeader->m_pNext;
	while (NULL != pMove->m_pNext) {
		if (dwCount-1 == dwIndex) {
			//get this place
			return pMove;
		}
		dwCount ++;
		pMove = pMove->m_pNext;
	}
	
	//the end
	return pMove;

	/* //test code
	//forward loop (only for test)
	//get the end node
	AL_Node<T>* pEnd = NULL;
	AL_Node<T>* pMove = NULL;
	//loop the next data;
	pMove = m_pHeader->m_pNext;
	while (NULL != pMove->m_pNext) {
		pMove = pMove->m_pNext;
	}
	pEnd = pMove;
	pMove = NULL;

	DWORD dwCount = Length();
	//loop the next data;
	pMove = pEnd;
	while (m_pHeader != pMove->m_pPre) {
		if (dwCount-1 == dwIndex) {
			//get this place
			return pMove;
		}
		dwCount --;
		pMove = pMove->m_pPre;
	}

	//the end
	return pMove;
	*/
}

#endif // CXX_AL_LISTDOUBLE_H
/* EOF */
